Today's network links carry vast amounts of information. High bandwidth applications supported by these network links include, for example, streaming video, streaming audio, and large aggregations of voice traffic. In the future, network bandwidth demands will increase. Certain applications, such as streaming audio and streaming video, can generate a large amount of network traffic due to sending such a transmission to multiple subscribers. In order to help decrease network traffic load due to such applications, multicast protocols have been developed.
Multicast protocols enable multicast transmission (i.e., one-to-many connections) by replicating a multicast data packet close to a destination of that packet, obviating the need for multiple unicast connections for the same purpose. Upon receiving a multicast packet, a network node, such as a network router, can examine a multicast group destination address (GDA) of the packet and determine whether subscribers to the multicast packet are connected directly or indirectly to the network node. The network node can then replicate the multicast packet as needed and transmit the multicast packet to any connected subscribing nodes.
FIG. 1A is a simplified block diagram illustrating a network configuration over which a multicast datastream can be transmitted. Network 100 includes network routers 110, 120, 130, 140, and 150. Network router 110 is coupled to a source S1 of a multicast datastream. Network router 120 is coupled to a network element N1 that is a subscriber to the multicast datastream from S1. As illustrated, an initial route through network 100 that the multicast datastream traverses is via network router 110 to network router 130 to network router 120. This data path through network 100 is a branch of a multicast distribution tree.
Data flow within a multicast distribution tree is defined in terms of upstream and downstream, wherein upstream is the direction toward the source of the multicast datastream while downstream is in the direction toward the subscriber nodes of the multicast datastream. Network routers in network 100 can use several different protocols, alone or in combination, to build a multicast distribution tree.
Each router within network 100 can store and access a forwarding information base that may include unicast routing information. A forwarding information base can include entries that relate a network prefix, an identifier of a next-hop router that is upstream toward that network prefix, and an identifier of a port on the router that is coupled to the next-hop router. A router can populate such a forwarding information base through the use of internal gateway protocols (IGPs) (e.g., routing information protocol (RIP) (as defined in RFC 1058 and RFC 2453), open-shortest-path-first protocol (OSPF) (as described in RFC 2328), intermediate system-to-intermediate system (IS-IS) (as described in ISO 1059), and border gateway protocol (BGP) (as described in RFC 1771). The forwarding information base allows a router to determine a best next-hop router toward a subnet identified by a network prefix.
When a subscriber network element (e.g., N1) wishes to join a multicast group in order to receive a multicast datastream from a source, the network node can send a request packet to a neighboring router (e.g., router 120). Upon receiving the request, router 120 can determine whether it is already a member of the multicast distribution tree that is transporting the datastream for the requested source and multicast group. The determination can be performed by referencing a multicast routing table that can include source and multicast group entries, also called multicast state entries (S,G), each of which includes an incoming interface for the multicast datastream, outgoing interfaces for the multicast datastream, and an identifier of the reverse path forwarding neighbor. If the multicast routing table does contain an entry related to the requested multicast state, then the entry in the multicast routing table can be modified to include an interface coupled to the requesting network node as an outgoing interface for the datastream. If no corresponding entry is present in the multicast routing table, then network router 120 can perform operations to join or form a multicast distribution tree coupled to the source of the requested multicast datastream.
In order to build a multicast distribution tree, network router 120 can perform a reverse path forwarding (RPF) check to determine the router interface that is topologically closest to the root of the tree. In a point-to-multipoint distribution tree, the root can be the source of the multicast transmission, while in a multipoint-to-multipoint distribution tree (also known as a shared distribution tree) the root can be a rendezvous point. The RPF check can be performed by referencing the forwarding information base to determine the next-hop router toward the root. Once the RPF check has been performed and an RPF interface has been identified, router 120 can transmit a join message from that interface to the next-hop router (e.g., router 130) indicating that router 120 wants to receive packets for this multicast group from the identified source. Such a message is a (S,G) join message, which can be formatted using a protocol such as protocol independent multicast (PIM). The upstream router, router 130, can provide an acknowledgement to router 120 and perform a similar set of tasks to form or join multicast distribution tree, if the multicast routing table lacks an entry for the requested source and multicast group. Through the use of information generated by RPF and join message acknowledgments, multicast routing table entries can be built by each multicast distribution tree router.
A multicast state entry is present in the multicast routing table for every multicast group for which a subscriber is coupled, either directly or indirectly, to the router. For a large network 100, thousands of multicast state entries may be present in the multicast routing table of any particular router. For example, in a multicast routing table in router 120, several hundred multicast entries can identify the interface coupled to router 130 as the incoming interface.
FIG. 1B is a simplified block diagram illustrating a change in a multicast distribution tree due to unavailability of router 130. A router can become unavailable for a variety of reasons, including failure of the router, maintenance of the router, or a disruption in the communication lines coupling an upstream router to a downstream router. If an upstream router that is part of a multicast distribution tree becomes unavailable, steps can be taken to avoid the unavailable router and provide a modified multicast distribution tree or branch on which to carry the datastream.
In FIG. 1B, when router 130 becomes unavailable, a series of actions are triggered that ultimately can form a modified multicast distribution tree that includes router 110 to router 140 to router 150 to router 120. When router 130 becomes unavailable, router 120, for example, can discover that change in the network through the use of an internal gateway protocol such as those described above. Once such a change is detected, an RPF check can determine that the original multicast distribution tree no longer works; that is, for example, an RPF neighbor address in the multicast routing table for a particular state can no longer be contacted.
As with the initial configuration of the multicast distribution tree, RPF in router 120 can select a new incoming interface using data in the forwarding information base (e.g., finding a next best neighboring router to the source network prefix). Once a new RPF neighbor address has been determined for a multicast state, a (S,G) join (e.g., PIM join message) can be transmitted to the newly identified upstream router (e.g., router 150). In such a manner, a new multicast distribution tree can be formed in order to carry the datastream from source S1 to subscriber N1. The process of modifying a multicast distribution tree is called convergence and involves each router that is a member of a multicast distribution tree distributing update messages that stimulate the recalculation of an optimal route from a receiver to a source of a multicast datastream.
In a large network scenario where there may be thousands of multicast distribution trees through routers 110, 130 and 120, and convergence in router 120 due to the unavailability of router 130 within the network can take a period of time that is linearly dependent upon the number of multicast entries in router 120's multicast routing table. Convergence time for any one of the multicast entries can depend upon where the entry falls within the multicast routing table. That is, if distribution tree modifications are performed in multicast routing table entry order, then the last entry in the multicast routing table will be updated much later than the first entry in the multicast routing table. Thus, those later entries can experience delays equal to the time it takes to discover the unavailability of router 130, plus the time it takes for all preceding affected entries in the multicast routing table to converge, plus the time it takes for the multicast distribution tree for that state entry to converge.
Link disruption detection and unicast path convergence performance can both be tuned to provide sub-second convergence in many network topologies. Multicast convergence time is not only dependent upon link disruption detection and unicast path convergence performance, but is also dependent upon a number of multicast routing table entries in a network router that depend on the link that was disrupted. In many routing architectures today, multicast distribution trees can converge approximately at a rate of 1,000 multicast routing table entries per second, but with no predictable performance guarantee for the order in which state entries in a multicast routing table will converge. The informational content of a multicast datastream being transmitted over a multicast distribution tree can have varying levels of operational importance (e.g., premium video services and other broadcast video can have a lower tolerance for disruption in a datastream than multicast services for virtual private networks (MVPN)). Current network and network router implementations cannot provide for predictable, repeatable convergence performance across a range of state entries or for each deployed multicast service.
What is therefore desired is an ability to ensure that in the case of many multicast entries in a multicast routing table that convergence can occur quickly for chosen classes of multicast datastreams. Such classes can be defined by a network administrator in accord with appropriate criteria. It is also desirable to ensure fair convergence for multicast entries of a same class. That is, for example, if a particular class has a large number of associated multicast entries, then the same states are not always treated at the end of any tree building or rebuilding operations.